package bintree.LeetCode;
import java.util.*;
//1028. 从先序遍历还原二叉树

/**
 * 第二次 用
 */
//public class Num1028_recoverFromPreorder {
//
//    public static TreeNode recoverFromPreorder(String traversal) {
//        Deque<TreeNode> path = new LinkedList<TreeNode>();
//        int pos = 0;
//        while (pos < traversal.length()) {
//            int level = 0;
//            while (traversal.charAt(pos) == '-') {
//                ++level;
//                ++pos;
//            }
//            int value = 0;
//            while (pos < traversal.length() && Character.isDigit(traversal.charAt(pos))) {
//                value = value * 10 + (traversal.charAt(pos) - '0');
//                ++pos;
//            }
//            TreeNode node = new TreeNode(value);
//            if (level == path.size()) {
//                if (!path.isEmpty()) {
//                    path.peek().left = node;
//                }
//            } else {
//                while (level != path.size()) {
//                    path.pop();
//                }
//                path.peek().right = node;
//            }
//            path.push(node);
//        }
//
//        while (path.size() > 1) {
//            path.pop();
//        }
//        return path.peek();
//    }
//
//    public static void main(String[] args) {
//        TreeNode root = recoverFromPreorder("1-401--349---90--88");
//        System.out.println();
//        System.out.println();
//        System.out.println();
//    }
//
//}











/**
 * 第一次写毁了
 */

//public class Num1028_recoverFromPreorder {
//    public static int index;//记录走到哪了
//    public static int pos;//记录整形数组里面数据的位置
//    public static TreeNode recoverFromPreorder(String traversal) {
//        String[] tmp = traversal.split("-");
//        //先让这个字符串把空格带好
//        StringBuilder str = new StringBuilder();
//        generateBSTString(str,traversal,0);
//
//        index = 0;
//        //设计一个方法，根据这个前序遍历字符串创建二叉树
//        TreeNode root = preOrderBuild( str.toString() );
//
//        return root;
//    }
//
//
//    /**
//     * 输入先序遍历待深度 - 的字符串，就是帮你添加好 #返回字符串
//     */
//    public static void generateBSTString(StringBuilder str, String trav, int k){
//        if(index == trav.length()){
//            return;
//        }
//        int h = 0;
//        while(trav.charAt(index) == '-'){
//                h ++;
//                index ++;
//        }
//        if(h != k){
//            //说明不在一个高度
//            str.append('#');
//            index -= h;
//            return;
//        }
//
//        str.append(trav.charAt(index));//添加一个元素
//        index ++;
//
//        generateBSTString(str, trav, k + 1);
//        generateBSTString(str, trav, k + 1);
//
//        return;
//    }
//
//    /**
//     * 入一个字符串str，就能按照前序遍历的方式还原为二叉树，返回根节点
//     */
//    private static TreeNode preOrderBuild(String str){
//        if(str.length() <= index){
//            return null;
//        }
//        char ch = str.charAt(index);
//        if(ch == '#' ){
//            return null;
//        }
//        int val = (int)(ch - '0');
//        TreeNode root = new TreeNode(val);
//        index ++;
//        root.left = preOrderBuild(str);
//        index ++;
//        root.right = preOrderBuild(str);
//
//        return root;
//    }
//
//    public static void main(String[] args) {
//        StringBuilder str = new StringBuilder();
//        String tav = "1-401--349---90--88";
//        String[] tmp = tav.split("-");
//
//        for(String i : tmp){
//            System.out.print(i + " ");
//        }
//
////        generateBSTString(str,tav, 0);
////        String aa = str.toString();
////        System.out.println(aa);
////        index = 0;
////        TreeNode root = preOrderBuild(aa);
////        System.out.println();
////        System.out.println();
//    }
//}

/**
 * 第三次
 */
public class Num1028_recoverFromPreorder {
    public static int index;//记录走到哪了
    public static int pos;//记录整形数组里面数据的位置
    public static TreeNode recoverFromPreorder(String traversal) {
        String[] tmp = traversal.split("-");//分割字符串，可以拿到里面的数据
        TreeNode root = generateBSTString(tmp, traversal, 0);

        return root;
    }

    private static TreeNode generateBSTString(String[] tmp, String traversal, int i) {
        if(index >= traversal.length()){
            return null;
        }
        int k = 0;
        //计算高度
        while(traversal.charAt(index) == '-'){
                index ++;
                k ++;
        }
        if(i != k){
            //不是一个高度的
            index -= k;
            return null;
        }
        //跳过整数
        while( index <  traversal.length() && traversal.charAt(index) != '-'){
            index ++;
        }
        //先让数据指向不为空
        while(tmp[pos].equals("")){
            pos ++;
        }

        //计算整数值
        int val = 0;
        for (int j = 0; j < tmp[pos].length(); j++) {
            val = val * 10 + (tmp[pos].charAt(j) - '0');
        }
        TreeNode root = new TreeNode(val);
        pos++;
        root.left = generateBSTString(tmp, traversal, i + 1);
        root.right = generateBSTString(tmp, traversal, i + 1);

        return root;
    }

    public static void main(String[] args) {
        String str = "1-401--349---90--88";
        String[] arr = str.split("-");
//        boolean is = false;
//        int p = 0;
//        while(arr[0].equals(" ")){
//            p++;
//        }
//        for(String i : arr){
//            System.out.print(i + "-");
//        }
//        System.out.println(arr[2].equals(""));


        TreeNode root = recoverFromPreorder(str);
        System.out.println();
        System.out.println();
    }
}